
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };
 
class Solution {
public:
    TreeNode* head = nullptr;
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,
        int& pi, int istart, int iend)
    {
        if (istart > iend) return nullptr;
        TreeNode* cur = new TreeNode(preorder[pi]);
        int curi = istart;
        while (curi <= iend)
        {
            if (preorder[pi] == inorder[curi])
            {
                break;
            }
            else
                curi++;
        }
        pi++;
        cur->left = _buildTree(preorder, inorder, pi, istart, curi - 1);
        cur->right = _buildTree(preorder, inorder, pi, curi + 1, iend);
        return cur;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int pi = 0, ii = 0;

        return _buildTree(preorder, inorder, pi, ii, inorder.size() - 1);

    }
};